package _03_recursion;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author: mornd
 * @dateTime: 2023/6/1 - 3:32
 * 递归实现插入排序
 */
public class InsertionSort {

    @Test
    public void test() {
        int[] arr = {4, 3, 2, 1, 87, 36, 21};
//        insertionArea(arr, 0, 4);
        insertion(arr);
        System.out.println(Arrays.toString(arr));
    }

    void insertion(int[] arr) {
        foo(arr, 1);
    }

    /**
     * 递归实现插入排序
     *
     * @param arr
     * @param low
     */
    private void foo(int[] arr, int low) {
        if (low == arr.length) {
            return;
        }
        int t = arr[low];
        int j = low - 1;
        while (j >= 0 && arr[j] > t) {
            arr[j + 1] = arr[j];
            j--;
        }

        if (j + 1 != low) { // 优化，当下标low不需要往前移动时（位置已找到），不用再重新赋值t
            arr[j + 1] = t;
        }
        foo(arr, low + 1);
    }

    void insertionArea(int[] arr, int start, int end) {
        if (start < 0 || end < 1 || end <= start || end > arr.length + 1) {
            throw new IllegalArgumentException();
        }
        fooArea(arr, start, start, end);
    }

    /**
     * 区间 [start - end) 排序
     *
     * @param arr         数组
     * @param originIndex 初始开始下标
     * @param start       已排序好区间最后一个元素的下标
     * @param end         截止下标（左闭右开）
     */
    private void fooArea(int[] arr, int originIndex, int start, int end) {
        if (start > end - 2) {
            return;
        }
        int t = arr[start + 1];
        int i = start;
        for (; i >= originIndex && arr[i] > t; i--) {
            arr[i + 1] = arr[i];
        }
        if (i != start) {
            arr[i + 1] = t;
        }
        fooArea(arr, originIndex, start + 1, end);
    }

    // 普通插入排序
    void insertion2(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int t = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > t) {
                arr[j + 1] = arr[j];
                j--;
            }
            if (j + 1 != i) {
                arr[j + 1] = t;
            }
        }
    }
}
